package com.itcam.recursion2;

/**
 * @author : Cammy.Wu
 * Description : 斐波那契数列-Leetcode 70
 */

public class Demo01Fibonacci {
    public static void main(String[] args) {
        /**
         * 兔子问题
         *      第一个月，有一对未成熟的兔子（黑色，注意图中个头较小）
         *      第二个月，它们成熟
         *      第三个月，它们能产下一对新的小兔子（蓝色）
         *      所有兔子遵循相同规律，求第  n  个月的兔子数
         */
//        int n = 6; // 假设计算第10个月的兔子对数
//        int result = f(n);
//        System.out.println("第 " + n + " 个月的兔子对数是: " + result);

        /**
         *  青蛙爬楼梯
         *      楼梯有  n  阶
         *      青蛙要爬到楼顶，可以一次跳一阶，也可以一次跳两阶
         *      只能向上跳，问有多少种跳法
         *
         * 青蛙跳台阶问题本质上是斐波那契数列从第二项开始
         */
        int n = 6; // 假设计算跳上6级台阶的跳法总数
        int result = climbStairs(n);
        System.out.println("跳上 " + n + " 级台阶的跳法总数是: " + result);
    }

    /**
     * 计算斐波那契数列的第 n 项。
     * 斐波那契数列的定义是：F(0) = 0，F(1) = 1, F(n) = F(n - 1) + F(n - 2)（n ≥ 2，n ∈ N*）
     *
     * @param n 斐波那契数列的项数，必须是非负整数
     * @return 斐波那契数列的第 n 项的值
     */
    public static int f(int n) {
        // 当 n 为 0 时，斐波那契数列的第 0 项为 0，直接返回 0
        if (n == 0) {
            return 0;
        }
        // 当 n 为 1 时，斐波那契数列的第 1 项为 1，直接返回 1
        if (n == 1) {
            return 1;
        }
        // 当 n 大于 1 时，根据斐波那契数列的定义，第 n 项等于第 n - 1 项加上第 n - 2 项
        return f(n - 1) + f(n - 2);
    }


    /**
     * 计算跳上 n 级台阶的跳法总数。
     * 跳法总数遵循递推公式：f(n) = f(n - 1) + f(n - 2)，其中 f(1) = 1，f(2) = 2。
     *
     * @param n 台阶的级数，必须是非负整数
     * @return 跳上 n 级台阶的跳法总数
     */
    public static int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

}